# -*- coding: utf-8 -*-
"""
Created on Tue May 17 14:58:42 2016
@author: yue
"""

import time

MAX_NUM = 100000
sleep_time = 0.1
# demo
"""
0,10,inf,inf,inf,9,15;
10,0,inf,inf,inf,2,inf;
inf,inf,0,inf,1,inf,10;
inf,inf,inf,0,7,inf,inf;
inf,inf,1,7,0,inf,12;
9,2,inf,inf,inf,0,3;
15,inf,10,inf,12,3,0
"""

"""
0,6,3,inf,inf,inf;
6,0,2,5,inf,inf;
3,2,0,3,4,inf;
inf,5,3,0,2,3;
inf,inf,4,2,0,5;
inf,inf,inf,3,5,0
"""

_ = float('inf')


def dij(arraylist, start, n):
    dis = [0] * n
    flag = [False] * n
    pre = [start] * n
    points = []
    k = start
    flag[k] = True
    for i in range(n):
        dis[i] = arraylist[k][i]
    for i in range(n - 1):
        mini = MAX_NUM
        for j in range(n):
            if not flag[j] and dis[j] < mini:
                mini = dis[j]
                k = j
        if k == start:  # 不连通
            return
        flag[k] = True
        for j in range(n):
            if dis[j] > dis[k] + arraylist[k][j]:
                dis[j] = dis[k] + arraylist[k][j]
                pre[j] = k
        points.append(k)
    dist = []
    path = []
    for point in points:
        dist.append(dis[point])
        path_point = []
        # while (pre[point] != start):
        #     path_point.insert(0, (pre[point], point))
        #     point = pre[point]
        # path_point.insert(0, (start, point))
        # path.append(path_point)
        while (pre[point] != start):
            path_point.insert(1, (pre[point] + 1, point + 1))
            point = pre[point]
        path_point.insert(1, (start + 1, point + 1))
        path.append(path_point)
    return points, dist, path


if __name__ == '__main__':
    graph3 = [
        [0, 4, 2, 5, _, _, _, _, _, _],
        [_, 0, _, _, 7, 5, _, _, _, _],
        [_, _, 0, _, _, 9, _, _, _, _],
        [_, _, _, 0, 2, _, 7, _, _, _],
        [_, _, _, _, 0, _, _, 4, _, _],
        [_, _, _, _, _, 0, _, _, _, 6],
        [_, _, _, _, _, _, 0, _, 3, _],
        [_, _, _, _, _, _, _, 0, _, 7],
        [_, _, _, _, _, _, _, _, 6, 8],
        [_, _, _, _, _, _, _, _, _, 0]
    ]
    point, dist, path = dij(graph3, 0, len(graph3))
    print(point)
    print(dist)
    print(path)
